#include <iostream>
using namespace std;

#include "ProgCommon.h"
#include "LinkedQueue.h"

int n;

struct QNode {
    QNode() {}
    QNode( int a_low, int a_high )
    {
        low = a_low;
        high = a_high;
    }

    int low;
    int high;
};

template<class T>
void ShowList( T a[], int from, int to )
{
    cout << "[ ";
    for ( int i = from; i <= to; i++ ) {
        cout << a[i] << " ";
    }
    cout << "]";
}

int part( int a[], int low, int high )
{
    int i = low;
    int x = a[low];

    for ( int j = low + 1; j <= high; j++ ) {
        if ( a[j] <= x ) {
            i++;
            if ( i != j )
                Swap( a[i], a[j] );
        }
    }
    Swap( a[low], a[i] );

    return i;
}

LinkedQueue<QNode> Q;
void QuickSortSimple( int a[], int low, int high )
{
    int w, i, j;
    QNode top;

    Q.Add( QNode( low, high ) );

    while ( !Q.IsEmpty() ) {
        Q.Delete( top );
        if ( top.low < top.high ) {
            printf( "\n (%2d, %2d) -- [ ", top.low, top.high );
            w = part( a, top.low, top.high );
            for ( i = 1; i < w; i++ )
                printf( "%d ", a[i] );
            ConSetColor( FG_YELLOW );
            printf( "%d ", a[w] );
            ConSetColor( COLOR_DEFAULT );
            for ( i = w+1; i <= n; i++ )
                printf( "%d ", a[i] );
            printf( "]" );
            Q.Add( QNode( top.low, w - 1 ) );
            Q.Add( QNode( w + 1, top.high ) );
        }
    }
}

int main()
{
    PROG_BANNER;
    RAND_SEED;

    n = RandomInt( 7, 12 );
    int *a = new int[n+1];

    for ( int i = 1; i <= n; i++ ) {
        a[i] = RandomInt( 1, 10 );
    }

    ConSetColor( FG_CYAN );
    printf( "Prog 4: Quicksort impl use queue\n" );
    ConSetColor( COLOR_DEFAULT );

    printf( "Random array is: " );
    ConSetColor( FG_GREEN );
    ShowList( a, 1, n );
    ConSetColor( COLOR_DEFAULT );

    QuickSortSimple( a, 1, n );

    printf( "\nSorted array is: " );
    ConSetColor( FG_RED );
    ShowList( a, 1, n );
    ConSetColor( COLOR_DEFAULT );

    printf( "\n" );
    PROG_BANNER;
    PROG_PAUSE;
    return 0;
}

